﻿// Coins POJ - 1742.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>


using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-1742

/*
有一天，托尼打开他的钱箱，发现里面有一些硬币。他决定去附近的一家商店买一块非常漂亮的手表。
他想付准确的价格（不找零），而且他知道价格不会超过 m，但他不知道手表的准确价格。
你要编写一个程序，读取 n、m、A1、A2、A3...An 和 C1、C2、C3...Cn，分别对应托尼价值 A1、A2、A3...An 的硬币数量，
然后计算托尼可以用这些硬币支付多少价格（从 1 到 m）。
输入
输入包含多个测试用例。每个测试用例的第一行包含两个整数 n(1<=n<=100),m(m<=100000).
第二行包含 2n 个整数，分别表示 A1,A2,A3...An,C1,C2,C3...Cn（1<=Ai<=100000,1<=Ci<=1000）。
最后一个测试用例后面有两个 0。
输出
在一行中输出每个测试用例的答案。

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

8
4
*/

const int N = 100010;
int n, m;
int val[N];
int cnt[N];


//tle 版本
//int dp[2][N];


//void solve() {
//	memset(dp,0,sizeof dp);
//	dp[0][0] = 1;
//	int curr = 1;
//	int prev = 0;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 0; j <= m; j++) {
//			dp[curr][j] |= dp[prev][j];
//			if (0 == dp[curr][j]) {
//				for (int k = 1; k <= cnt[i]; k++) {
//					if (j >= k * val[i]) {
//						dp[curr][j] |= dp[prev][j - k * val[i]];
//					}
//				}
//			}
//		}
//		swap(curr, prev);
//	}
//
//	int ans = 0;
//	for (int i = 1; i <= m; i++) {
//		if (dp[prev][i]) ans++;
//	}
//
//	cout << ans << endl;
//}




int dp[2][N];

void solve1() {
	memset(dp, -1, sizeof dp);
	dp[0][0] = 0;
	int prev = 0;
	int curr = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (dp[prev][j] >= 0) dp[curr][j] = 0;
			else if (j >= val[i] && dp[curr][j - val[i]] >= 0 &&
				dp[curr][j - val[i]] < cnt[i])
			{
				dp[curr][j] = dp[curr][j - val[i]] + 1;
			}
		}
		swap(prev, curr);
	}

	int ans = 0;
	for (int i = 1; i <= m; i++) {
		if (dp[prev][i] >= 0) ans++;
	}
	cout << ans << endl;

}


int main()
{
	while (cin >> n >> m) {
		if (0 == n && 0 == m)break;
		for (int i = 1; i <= n * 2; i++) {
			if (i <= n) { cin >> val[i];}
			else { cin >> cnt[i - n]; }
		}

		solve1();
	}


	return 0;
}

 